#ifndef STACK_H_
#define STACK_H_

// a Stack is a delist of several UnitStacks and each UnitStack is implemented by an array
template<typename T>
class Stack
{
  private:
    class UnitStackList
    {
      private: // UnitStackList
        const static int _InitUnitStackSize = 50;
        const static int _IncFactor = 2;

        class UnitStack
        {
          private: // UnitStack
            T **_pTarray;
            int _top; // 0 ~ _capacity
            const int _capacity;
            UnitStack *_pNext;
            UnitStack *_pPrev;
          public: // UnitStack
            UnitStack(int);
            ~UnitStack();
            int capacity() const {return _capacity;}
            int top()const{return _top;}
            UnitStack *&next() {return _pNext;}
            UnitStack *&prev() {return _pPrev;}
            T *topptr()const{return _pTarray[_top];}
            T *pop(){return _pTarray[--_top];}
            void push(T *pT){_pTarray[_top++] = pT;}
        }; // UnitStack		
        UnitStack *_head, *_tail;

      public: // UnitStackList
        UnitStackList(int);
        ~UnitStackList();
        T *top()const;
        T *pop(); // ***
        void push(T *); // ***
        bool isEmpty();
    }; // UnitStackList

    UnitStackList *_uslist;

  public: // Stack
    Stack();
    ~Stack();
    T *top() const { return _uslist->top();  }
    T *pop(){return _uslist->pop();}
    void push(T *pT){_uslist->push(pT);}
    bool isEmpty(){ return _uslist->isEmpty(); }
}; // Stack

// implementation

  template<typename T>
  Stack<T>::UnitStackList::UnitStack::UnitStack(int n = 0)
:_pTarray(0),_top(0),_capacity(n),_pNext(0),_pPrev(0)
{
  if(n)
    _pTarray = new T*[n];
}

  template<typename T>
Stack<T>::UnitStackList::UnitStack::~UnitStack()
{ delete []_pTarray; }

template<typename T> 
const int Stack<T>::UnitStackList::_InitUnitStackSize;

template<typename T> 
const int Stack<T>::UnitStackList::_IncFactor;

  template<typename T>
  Stack<T>::UnitStackList::UnitStackList(int n = _InitUnitStackSize)
:_head(new UnitStack(n)),_tail(_head)
{}

  template<typename T>
Stack<T>::UnitStackList::~UnitStackList()
{
  UnitStack *tmp = _head, *tmpnext = 0;
  _head = _tail = 0;
  while(tmp)
  {
    tmpnext = tmp->next();
    delete tmp;
    tmp = tmpnext;
  }
}

template<typename T> 
T *Stack<T>::UnitStackList::top() const
{ return _tail->topptr(); }

  template<typename T> 
T *Stack<T>::UnitStackList::pop()
{
  if(!_tail->top())
    _tail = _tail->prev();
  // heuristicly free some redundant memory
  if(_tail->next() && (_tail->top() < _tail->capacity()/2))
  {
    delete _tail->next();
    _tail->next() = 0;
  }
  if(_tail)
    return _tail->pop();
  else // Stack is empty. The result of pop() is undefined.
    return 0;
}

  template<typename T> 
void Stack<T>::UnitStackList::push(T *pT)
{
  if(_tail->top()==_tail->capacity())
    if(!_tail->next())
    { // push_back
      _tail->next() = new UnitStack(_IncFactor * _tail->capacity());
      _tail->next()->prev() = _tail;
      _tail = _tail->next();
    }
    else
      _tail = _tail->next();

  _tail->push(pT);
}

  template<typename T> 
bool Stack<T>::UnitStackList::isEmpty()
{
  if(_head==_tail && !_head->top())
    return true;
  else
    return false;
}

  template<typename T>
Stack<T>::Stack():_uslist(new UnitStackList)
{}

  template<typename T> 
Stack<T>::~Stack()
{ delete _uslist; _uslist=0;}

#endif /*STACK_H_*/

